package org.example;

import java.util.Arrays;

public class Test3 {
    /**
     * 方法一：速度慢
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1000);
        for (int i = n - 2; i >= 0; i--) {
            if (i + nums[i] >= n - 1) dp[i] = 1;
            else {
                for (int j =  i + 1; j <= i + nums[i]; j++) {
                    dp[i] = Math.min(dp[i],dp[j] + 1);
                }
            }
        }
        return dp[0];
    }

    public int jump1(int[] nums) {
        int step = 0, end = 0, rightMost = 0, n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            rightMost = Math.max(rightMost,i + nums[i]);
            if (i == end) {
                end = rightMost;
                step++;
            }
        }
        return step;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,1,1,1};
        Test3 test3 = new Test3();
        test3.jump(arr);
        System.out.println(999);
    }
}
